package com.atguigu.single.linklist;

import com.atguigu.single.Node;

import java.util.Stack;

/**
 * @ClassName SingleLinkList
 * @DeScription 单向链表实现
 * @Author 剧情再美终是戏
 * @Date 2019/11/19 20:15
 * @Version 1.0
 **/
public class SingleLinkList {

    // 初始化一个头节点，这个节点不存储数据
    Node head = new Node(0, "", "");

    // 添加一个节点
    public void add(Node node) {
        // 添加一个辅助节点
        Node tmp = head;

        // 循环遍历找到最后一个节点
        for (; ; ) {
            if (null == tmp.getNext()) {
                break;
            }
            tmp = tmp.getNext();
        }

        // 向最后一个节点添加一个节点
        tmp.setNext(node);
    }

    // 添加一个节点带顺序的
    public void addByOrder(Node node) {

        // 添加一个辅助节点
        Node tmp = head;

        // 记录是否已经存在这个id的节点
        boolean flag = false;

        for (; ; ) {
            Node next = tmp.getNext();
            if (null == next) {
                break;
            }
            if (node.getId() < next.getId()) {
                break;
            } else if (node.getId() == next.getId()) {
                flag = true;
                break;
            }
            tmp = next;
        }

        if (flag) {
            System.out.printf("id为%d的节点已经存在了，添加失败！\n", node.getId());
            return;
        } else {
            // 将当前需要添加的节点指向tmp.next
            node.setNext(tmp.getNext());
            // 将tmp.next指向当前添加的节点
            tmp.setNext(node);
        }
    }

    // 修改一个节点
    public void udate(Node node) {

        // 添加一个辅助节点
        Node tmp = head;

        // 添加一个标记位，标记是否找到这个节点
        boolean flag = false;

        for (; ; ) {
            Node next = tmp.getNext();
            if (null == next) {
                break;
            }
            if (node.getId() == next.getId()) {
                flag = true;
                break;
            }
            tmp = next;
        }
        if (flag) {
            tmp.getNext().setName(node.getName());
            tmp.getNext().setDes(node.getDes());
        } else {
            System.out.printf("没有找到id为%d的节点，修改失败！\n", node.getId());
        }
    }

    // 删除一个节点
    public void del(int no) {

        // 添加一个辅助节点
        Node tmp = head;

        // 添加一个标记位，标记是否找到这个节点
        boolean flag = false;

        for (; ; ) {
            Node next = tmp.getNext();
            if (null == next) {
                break;
            }
            if (no == next.getId()) {
                flag = true;
                break;
            }
            tmp = next;
        }

        if (flag) {
            // 将tmp.next设置为tmp.next.next
            tmp.setNext(tmp.getNext().getNext());
        } else {
            System.out.print("没有找到id为%d的节点，删除失败！\n");
        }
    }

    // 输出所有节点
    public void list() {

        // 添加一个辅助节点
        Node tmp = head;

        if (null == tmp.getNext()) {
            System.out.println("集合为空了");
            return;
        }

        for (; ; ) {
            Node next = tmp.getNext();
            if (null == next) {
                break;
            }
            System.out.println(next);
            tmp = next;
        }
    }

    //  获取链表的有效节点数量
    public int size() {

        // 添加一个辅助节点
        Node tmp = head;

        if (null == tmp.getNext()) {
            return 0;
        }

        int size = 0;
        while (null != tmp.getNext()) {
            size++;
            tmp = tmp.getNext();
        }
        return size;
    }

    // 获取节点倒数第K个节点
    public Node getLastN(int k) {

        // 添加一个辅助节点
        Node tmp = head;

        if (null == tmp.getNext()) {
            return null;
        }

        // 选获取集合的有效节点数量
        int size = size();

        // 参数过滤
        if (0 >= k || k > size) {
            return null;
        }

        // 获取倒数第K个节点
        int i = size - k;
        while (i >= 0) {
            tmp = tmp.getNext();
            i--;
        }
        return tmp;
    }


    // 将链表反转
    public void veversal() {
        // 添加一个辅助节点
        Node tmp = head;

        // 为空或者只有一个节点都不需要反转
        if (null == tmp.getNext() || null == tmp.getNext().getNext()) {
            return;
        }

        // 添加一个反转集合的装载容器
        Node veversalNode = new Node(0, "", "");

        while (null != tmp && null != tmp.getNext()) {

            // 获取当前操作的节点
            Node next = tmp.getNext();

            // 将当前指针移动到后一个节点
            tmp.setNext(next.getNext());

            // 将当前节点指向veversalNode的下一个节点
            next.setNext(veversalNode.getNext());

            // 将veversalNode的下一个节点指定当前节点
            veversalNode.setNext(next);
        }

        // 将原来的集合的下一个节点指定veversalNode的下一个节点
        head.setNext(veversalNode.getNext());
    }

    // 倒序打印
    public void veversalPrint() {
        // 添加一个辅助节点
        Node tmp = head;

        // 为空不做操作
        if (null == tmp.getNext()) {
            return;
        }

        // 添加一个栈集合
        Stack<Node> stack = new Stack();

        // 按顺序将链表中的数据添加到栈中
        for (; ; ) {
            Node next = tmp.getNext();
            if (null == next) {
                break;
            }
            stack.add(next);
            tmp = next; // 后移
        }

        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}
